#include <iostream>
#include <vector>

int BinarySearch(std::vector<int> const &_vec, int const _n)
{
    auto s = _vec.begin();
    auto e = _vec.end();

    while (s < e)
    {
        auto m = s + (e - s) / 2;

        if (*m == _n)
        {
            s = m + 1;
        }
        else if (*m < _n)
        {
            s = m + 1;
        }
        else if (*m > _n)
        {
            e = m;
        }
    }

    if (e <= _vec.begin() || e == _vec.end() || *(e - 1) != _n)
    {
        return -1;
    }
    return e - _vec.begin();
}

int main()
{
    std::vector<int> vec1 = {-1, 0, 3, 5, 9, 12};
    std::cout << "Binary Search: " << BinarySearch(vec1, 2) << std::endl;

    std::vector<int> vec2 = {-1, 0, 3, 5, 9, 12};
    std::cout << "Binary Search: " << BinarySearch(vec2, 5) << std::endl;

    std::vector<int> vec3 = {-1, 0, 3, 3, 9, 12, 15};
    std::cout << "Binary Search: " << BinarySearch(vec3, 3) << std::endl;

    std::vector<int> vec4 = {1, 1, 1, 1, 1, 1, 1};
    std::cout << "Binary Search: " << BinarySearch(vec4, 1) << std::endl;

    return 0;
}